package leetcode.lt100;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

class Solution_84 {

    public static void main(String[] args) {
//        int[] heights = new int[]{2, 1, 5, 6, 2, 3};
        int[] heights = new int[]{2, 1, 2};
        System.out.println(largestRectangleArea(heights));
    }

//    public int largestRectangleArea(int[] heights) {
//        int l = heights.length;
//        if (l == 0) {
//            return 0;
//        }
//        if (l == 1) {
//            return heights[0];
//        }
//        int max = heights[0];
//        //i代表矩形左边
//        for (int i = 0; i < l; i++) {
//            int minHeight = heights[i];
//            //j代表矩形右边
//            for (int j = i; j < l; j++) {
//                minHeight = Math.min(minHeight, heights[j]);
//                max = Math.max((j - i + 1) * minHeight, max);
//            }
//        }
//        return max;
//    }

//    public static int largestRectangleArea(int[] heights) {
//        return largestRectangleArea(heights, 0, heights.length - 1);
//    }
//
//    private static int largestRectangleArea(int[] heights, int start, int end) {
//        if (start < 0 || end > heights.length - 1 || end < start) {
//            return 0;
//        }
//        if (start == end) {
//            return heights[start];
//        }
//        int minHeightIndex = start;
//        for (int i = start; i <= end; i++) {
//            if (heights[i] < heights[minHeightIndex]) {
//                minHeightIndex = i;
//            }
//        }
//        return Math.max((end - start + 1) * heights[minHeightIndex], Math.max(largestRectangleArea(heights, start, minHeightIndex - 1), largestRectangleArea(heights, minHeightIndex + 1, end)));
//    }

//    public static int largestRectangleArea(int[] heights) {
//        int res = 0;
//        Deque<Integer> stack = new ArrayDeque<>();
//        stack.push(-1);
//        for (int i = 0; i < heights.length; i++) {
//            while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
//                res = Math.max(res, (i - stack.peek()) * heights[stack.pop()]);
//            }
//            stack.push(i);
//        }
//        while (stack.peek() != -1)
//            res = Math.max(res, heights[stack.pop()] * (heights.length - stack.peek() -1));
//        return res;
//    }

    public static int largestRectangleArea(int[] heights) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        int[] new_heights = new int[heights.length + 2];
        for (int i = 1; i < heights.length + 1; i++) new_heights[i] = heights[i - 1];
        for (int i = 0; i < new_heights.length; i++) {
            while (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {
                Integer cur = stack.pop();
                res = Math.max(res, new_heights[cur] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }

}